ebab7d0da53c51438720d60c6e2e467c - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Ruler function</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Ruler function</span></span>

</h1>

</header>

<p>In <a href="Number_theory" title="Number theory">number theory</a>, the <b>ruler function</b> of an integer <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> can be either of two closely related functions. One of these functions counts the number of times <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</p>

/* start https://en.wikipedia.org/ */

.mw-parser-output .block-indent{padding-left:3em;padding-right:0;overflow:hidden}

/* end https://en.wikipedia.org/ */

</style><div class="block-indent">0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, ... (sequence <span class="nowrap external"><a href="https://oeis.org/A007814" class="extiw external" title="oeis:A007814">A007814</a></span> in the <a href="On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>).</div>

<p>Alternatively, the ruler function can be defined as the same numbers plus one, which for the numbers 1, 2, 3, ... produces the sequence

</p>

<div class="block-indent">1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, ... (sequence <span class="nowrap external"><a href="https://oeis.org/A001511" class="extiw external" title="oeis:A001511">A001511</a></span> in the <a href="On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>).</div>

<p>As well as being related by adding one, these two sequences are related in a different way: the second one can be formed from the first one by removing all the zeros, and the first one can be formed from the second one by adding zeros at the start and between every pair of numbers. For either definition of the ruler function, the rising and falling patterns of the values of this function resemble the lengths of marks on <a href="Ruler" title="Ruler">rulers</a> with traditional units such as <a href="Inch" title="Inch">inches</a>. These functions should be distinguished from <a href="Thomae's_function" title="Thomae's function">Thomae's function</a>, a function on <a href="Real_number" title="Real number">real numbers</a> which behaves similarly to the ruler function when restricted to the <a href="Dyadic_rational_number" class="mw-redirect" title="Dyadic rational number">dyadic rational numbers</a>.

</p><p>In advanced mathematics, the 0-based ruler function is the <a href="P-adic_valuation" title="P-adic valuation">2-adic valuation</a> of the number,<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> and the <a href="Lexicographic_order" title="Lexicographic order">lexicographically earliest</a> infinite <a href="Square-free_word" title="Square-free word">square-free word</a> over the natural numbers.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> It also gives the position of the bit that changes at each step of the <a href="Gray_code" title="Gray code">Gray code</a>.<sup id="cite_ref-herter-rote_3-0" class="reference"><a href="#cite_note-herter-rote-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p><p>In the <a href="Tower_of_Hanoi" title="Tower of Hanoi">Tower of Hanoi</a> puzzle, with the disks of the puzzle numbered in order by their size, the 1-based ruler function gives the number of the disk to move at each step in an optimal solution to the puzzle.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> A simulation of the puzzle, in conjunction with other methods for generating its optimal sequence of moves, can be used in an algorithm for generating the sequence of values of the ruler function in <a href="Constant_time" class="mw-redirect" title="Constant time">constant time</a> per value.<sup id="cite_ref-herter-rote_3-1" class="reference"><a href="#cite_note-herter-rote-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFEricksonIsgurJacksonRuskey2012" class="citation journal cs1">Erickson, Alejandro; Isgur, Abraham; Jackson, Bradley W.; Ruskey, Frank; Tanny, Stephen M. (January 2012). <a rel="nofollow" class="external text" href="http://epubs.siam.org/doi/10.1137/100795425">"Nested Recurrence Relations with Conolly-like Solutions"</a>. <i>SIAM Journal on Discrete Mathematics</i>. <b>26</b> (1): <span class="nowrap">206–</span>238. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1509.02613">1509.02613</a></span>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2015arXiv150902613E">2015arXiv150902613E</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F100795425">10.1137/100795425</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0895-4801">0895-4801</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:8116882">8116882</a>.</cite></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite id="CITEREFGuay-PaquetShallit2009" class="citation journal cs1">Guay-Paquet, Mathieu; Shallit, Jeffrey (November 2009). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.disc.2009.06.004">"Avoiding squares and overlaps over the natural numbers"</a>. <i>Discrete Mathematics</i>. <b>309</b> (21): <span class="nowrap">6245–</span>6254. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/0901.1397">0901.1397</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.disc.2009.06.004">10.1016/j.disc.2009.06.004</a></span>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:8646044">8646044</a>.</cite></span>

</li>

<li id="cite_note-herter-rote-3"><span class="mw-cite-backlink">^ <a href="#cite_ref-herter-rote_3-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-herter-rote_3-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFHerterRote2018" class="citation journal cs1">Herter, Felix; Rote, Günter (November 2018). <a rel="nofollow" class="external text" href="https://linkinghub.elsevier.com/retrieve/pii/S0304397517308472">"Loopless Gray code enumeration and the Tower of Bucharest"</a>. <i>Theoretical Computer Science</i>. <b>748</b>: <span class="nowrap">40–</span>54. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1604.06707">1604.06707</a></span>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2016arXiv160406707H">2016arXiv160406707H</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.tcs.2017.11.017">10.1016/j.tcs.2017.11.017</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:4014870">4014870</a>.</cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFHinzKlavžarMilutinovićPetr2013" class="citation book cs1">Hinz, Andreas M.; Klavžar, Sandi; Milutinović, Uroš; Petr, Ciril (2013). <a rel="nofollow" class="external text" href="http://link.springer.com/10.1007/978-3-0348-0237-6"><i>The Tower of Hanoi – Myths and Maths</i></a>. Basel: Springer Basel. pp. <span class="nowrap">60–</span>61. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-0348-0237-6">10.1007/978-3-0348-0237-6</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-0348-0236-9</bdi>.</cite></span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><span class="citation mathworld" id="Reference-Mathworld-Ruler_function"><cite id="CITEREFWeisstein" class="citation web cs1"><a href="Eric_W._Weisstein" title="Eric W. Weisstein">Weisstein, Eric W.</a> <a rel="nofollow" class="external text" href="https://mathworld.wolfram.com/RulerFunction.html">"Ruler function"</a>. <i><a href="MathWorld" title="MathWorld">MathWorld</a></i>.</cite></span></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .asbox{position:relative;overflow:hidden}.mw-parser-output .asbox table{background:transparent}.mw-parser-output .asbox p{margin:0}.mw-parser-output .asbox p+p{margin-top:0.25em}.mw-parser-output .asbox-body{font-style:italic}.mw-parser-output .asbox-note{font-size:smaller}.mw-parser-output .asbox .navbar{position:absolute;top:-0.75em;right:1em;display:none}.mw-parser-output :not(p):not(.asbox)+style+.asbox,.mw-parser-output :not(p):not(.asbox)+link+.asbox{margin-top:3em}

/* end https://en.wikipedia.org/ */

</style></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-07-21" href="https://en.wikipedia.org/wiki/?title=Ruler_function&oldid=1235752049">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>